#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/6 8:43
@Author  : Chen Liu
@FileName: reverse_list.py
@Software: PyCharm
"""


class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class Node:
    def __init__(self, data):
        self.data = data
        self.root = None

    def create_list(self):
        if not self.data:
            return
        index = 0
        root = ListNode(self.data[index])
        node = root
        for index in range(1, len(self.data)):
            node.next = ListNode(self.data[index])
            node = node.next

        return root

    def print_node(self, root):
        # if not root:
            # return

        while root:
            print(root.val)
            root = root.next

    def reverse_list(self, root):
        """迭代"""
        if not root:
            return

        head = None
        p = root

        while p:
            q = p.next
            p.next = head
            head = p
            p = q

        return head

    def reverse_node(self, root):
        """递归迭代"""
        # 当节点为空或没有下一个节点时，返回该节点
        if not root or not root.next:
            return root

        res = self.reverse_node(root.next)
        # 反转链表
        root.next.next = root
        # 反转后原来的节点应该指向空节点，否则会出现循环
        root.next = None

        return res

    def test(self):
        self.root = self.create_list()
        self.print_node(self.root)
        root = self.reverse_list(self.root)
        self.print_node(root)
        res = self.reverse_node(root)
        self.print_node(res)


if __name__ == "__main__":
    data = [1, 2, 3, 4, 5]
    node = Node(data)
    node.test()
